package com.sunny.example.dfs;

import java.util.Scanner;

/**
 * 最长连续子串
 */
public class DfsTest {
    static int defSubLen = -1;//默认连续子序列长度为-1
    static int sum = 0;
    static int[] used;

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str1 = "";
            defSubLen = -1;
            sum = 0;

            String[] subInts = null;
            for (int i = 2; i > 0; i--) {
                if (i == 2) {
                    str1 = scanner.nextLine();
                    subInts = str1.split(",");
                } else {
                    sum = Integer.parseInt(scanner.nextLine());
                }
            }
            if (subInts == null || subInts.length == 0) {
                continue;
            }

            used = new int[subInts.length];//用过的元素

            //边界值
            for (int i = 0; i < subInts.length; i++) {
                int firstValue = Integer.parseInt(subInts[i]);//初始值
                if (i + 1 < subInts.length) {
                    calcDFS(firstValue, i + 1, subInts, 1);
                }
            }

//            System.out.println(defSubLen > -1 ? defSubLen + 1 : defSubLen);
            System.out.println(defSubLen);

        }
    }

    /**
     * DFS计算
     *
     * @param firstValue
     * @param index
     * @param subInts
     * @param len        步数
     */
    private static void calcDFS(int firstValue, int index, String[] subInts, int len) {
        if (firstValue != sum && index + 1 >= subInts.length) {
            //路径大于数组长度
            return;
        }
        for (int i = index; i < subInts.length; i++) {
            int current = Integer.parseInt(subInts[i]);
            firstValue += current;
            if (firstValue == sum && used[i] == 0) {
                if (len > defSubLen) {
                    defSubLen = len;
                }
                used[i] = 1;
                return;
            } else if (firstValue != sum && used[i] == 0) {//超出边界的，递归,DFS的核心是全部遍历
                len += 1;
                used[i] = 1;
                //1、如果连加的值>目标值，且后面还有值，则要舍掉当前的值
                //2、如果连加的值<目标值，且后面还有值，则继续累加
                calcDFS(firstValue > sum ? (firstValue - current) : firstValue, index + 1, subInts, len);
                used[i] = 0;
            }
        }

    }

}
